class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        f = [False] * (n + 1)
        f[0] = True
        i=1
        # while i< n+1""
        for i in range(1, n + 1):
            for j in range(i-1,-1,-1):
                if f[j]:
                    if s[j:i] in wordDict:
                        f[i] = True
                        break

        return f[-1]

s = "leetcode"
wordDict = ["leet", "code"]
s1 = Solution()
m = s1.wordBreak(s,wordDict)
print(m)